package cm.unit2.theme3;

import java.util.Arrays;

import cm.commom.TreeNode;

public class ReConstructBinaryTree {
	
	public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
		if(pre!=null&&pre.length>0) {
			TreeNode root = new TreeNode(pre[0]);
			int i = 0;
			// 划分
			for (; i < in.length; i++) {
				if (in[i]==pre[0]) {
					break;
				}
			}
			if (i!=0) {// 如果有左子树
				// 前序左
				int []newPreLeft = Arrays.copyOfRange(pre, 1,i+1);
				int []newInLeft = Arrays.copyOfRange(in, 0,i);
				root.left = reConstructBinaryTree(newPreLeft,newInLeft);
			}
			if (i!=pre.length-1) {// 如果有右子树
				// 前序右
				int []newPreRight = Arrays.copyOfRange(pre, i+1,pre.length);
				int []newInRight = Arrays.copyOfRange(in, i+1,in.length);
				root.right = reConstructBinaryTree(newPreRight, newInRight);
			}
			return root;
		}
		return null;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ReConstructBinaryTree func = new ReConstructBinaryTree();
		int []pre = {1,2,3,4,5,6,7};
		int []in = {3,2,4,1,6,5,7};
		TreeNode treeNode = func.reConstructBinaryTree(pre, in);
		System.out.println(treeNode);
		System.out.println("-----------");
	}

}
